package 代码随想录.单调栈.下一个更大元素II;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class LeetCode503 {
    //方法一：将数组复制一倍当作循环数组，
    // 对复制后的数组使用单调栈计算下一个更大元素，最后截取前nums.length长度即可
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] res = new int[len * 2];
        Arrays.fill(res, -1);
        //使用2倍的nums数组
        int[] arr = new int[len * 2];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = nums[i % nums.length];
        }
        //计算下一个更大的数值
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            int current = arr[i];
            //当前元素大于栈顶元素，找到了
            while (!stack.isEmpty() && current > arr[stack.peek()]) {
                Integer pop = stack.pop();
                res[pop] = current;
            }
            stack.push(i);
        }
        return Arrays.stream(res).limit(len).toArray();
    }

    //方法二：循环数组+单调栈
    public int[] nextGreaterElements1(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < 2 * n; i++) {
            int current = nums[i % n];
            while (!stack.isEmpty() && current > nums[stack.peek()]) {
                Integer pop = stack.pop();
                res[pop] = current;
            }
            stack.push(i % n);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 1};
        LeetCode503 code503 = new LeetCode503();
        int[] ints = code503.nextGreaterElements(nums);
        int[] ints1 = code503.nextGreaterElements1(nums);
        System.out.println(Arrays.toString(ints));
        System.out.println(Arrays.toString(ints1));
    }
}
